import java.awt.*;

public class Linkedlist {
    /*1.首先得知道单链表最基础的概念，单链表是由一个一个节点构成的  每个节点由数值域和节点域组成
    * 2.还要知道节点是怎么创建的  将节点通过类 ListNode 来抽象出来   new一个就有一个节点
    * 3.数值域的类型为数值类型 节点域为节点类型  Person p=new Person()  LNode node = new Lnode()
    * 4.创建一个节点类型的头结点引用来表示出那个节点是第一个节点
    * */
    public ListNode head;
    public ListNode cur;

    //最垃圾的第一步，通过穷举法创建一个链表出来
    //1.1通过实例化节点类来创建节点
    public void createList(){
        ListNode listnode1 = new ListNode(11);
        ListNode listnode2 = new ListNode(22);
        ListNode listnode3 = new ListNode(33);
        ListNode listnode4 = new ListNode(44);

        //1.2将节点通过next串起来  如果下面这句代码不写在函数里面会报错
        listnode1.next = listnode2;
        listnode2.next = listnode3;
        listnode3.next = listnode4;
        //1.3 将listnode1这个引用 引用的对象赋值给head
        this.head = listnode1;
    }

    //2.1.节点创建成功之后需要打印出来看看 需要用到循环->使用什么循环 while循环
    //2.2 循环的各种条件是啥->节点的地址不为空
    public void display(){
        this.cur=this.head;
        while(this.cur!=null){
            System.out.print(this.cur.val+" ");
            this.cur=this.cur.next;
        }
    }
    //2.3 打印有返回值的
    public void display1(ListNode newhead){
        ListNode cur=newhead;
        while(cur!=null){
            System.out.print(cur.val+" ");
            cur = cur.next;
        }
    }

    //3 得到单链表的长度
    public int size(){
        int count=0;
        //不要像这样重定义  ListNode cur = this.head;
        this.cur = this.head;
        while(this.cur != null){
            count++;
            this.cur = this.cur.next;
        }
        return count;
    }


    //4.头插法
    public void addFirst(int data){
        ListNode node = new ListNode(data);
        //先绑定后面的节点 即将head节点的地址赋给新插入的头结点的next域
        node.next = this.head;
        head = node;
    }

    //5.尾插法
    public void addLast(int data){
        ListNode node = new ListNode(data);

        //如果链表为空  cur.next就会导致空指针异常
        if(this.head == null){
            head = node;
        }else{
            this.cur = this.head;
            while(cur.next != null){
                this.cur = this.cur.next;
            }
            this.cur.next = node;
        }
    }

    //6.任意位置插入,第一个数据节点为0号下标
    public void addIndex(int index,int data){
        if(index<0 || index>size()){
            System.out.println("你输入的位置有误，请重新输入");
            return;
        }
        if(index==0){
            addFirst(data);
        }
        if(index==size()){
            addLast(data);
        }

        ListNode cur = findIndexSubOne(index);
        ListNode node = new ListNode(data);
        //先把后面的节点绑上
        node.next = cur.next;
        //再把前面的节点绑上
        cur.next = node;
        return;
    }

    //6.1 找到要插入的下标位置的节点
    public ListNode findIndexSubOne(int index) {
        this.cur = this.head;
        for (int i = 0; i < index-1; i++) {
            this.cur = this.cur.next;
        }
        return this.cur;
    }
    //7.查找是否包含关键字key是否在单链表当中
    public boolean contains(int key){
        this.cur = this.head;
        while (cur!=null){
            if(this.cur.val == key){
                return true;
            }
            this.cur = this.cur.next;
        }
        return false;
    }
    //8.回收所有节点，涉及到内存泄露问题
    public void clear(){
        //有两种方法，一种粗暴方法
        //this.head = null;
        //第二种方法，一个一个置空 需要创建一个curNext引用
        this.cur = this.head;
        while(cur!=null){
            ListNode curNext = this.cur.next;
            this.cur = null;
            this.cur = curNext;
        }
        this.head = null;
        return;
    }

    //9.删除第一次出现关键字为key的节点   prev.next = del.next
    public void remove(int key){
        //头结点是要删除的节点
        if(key == this.head.val){
            this.head = this.head.next;
            return;
        }
        ListNode prev = searchPrev(key);
        //如果没有找到
        if(prev == null) {
            System.out.println("没有你要删除的节点！");
            return;
        }
        //找到了
        ListNode del = prev.next;
        prev.next = del.next;
        return;
    }
    //9.1根据待删除的val值返回前驱节点
    public ListNode searchPrev(int key){
        ListNode pre = this.head;
        while(pre.next != null){
            if(pre.next.val==key){
                return pre;
            }
            pre=pre.next;
        }
        return null;//代表没有这样的前驱节点
    }

    //10. 删除所有值为key的节点 只遍历链表一遍
    public void removeAllKey(int key){
        ListNode prev = this.head;
        this.cur = prev.next;
        while(this.cur!=null){
            if(this.cur.val == key){
                prev.next = this.cur.next;
                this.cur= this.cur.next;
            }else{
                prev=this.cur;
                this.cur = this.cur.next;
            }
        }
        //上面的循环没有判断头节点的val值
        //这个if语句如果放在前面 必须写循环 判断每个头节点的值
        if(this.head.val==key){
            this.head = this.head.next;
        }
    }
    //11. 给你单链表的头节点 head ，请你反转链表，并返回反转后的链表（2种做法）
    //第一种：head cur代表要反转的节点 curNext
    public ListNode reverseList(){
        if(this.head == null){
            return null;
        }
        if(this.head.next==null){
            return this.head;
        }
        this.cur = this.head;
        ListNode curNext = this.cur.next;
        this.cur.next = null;
        cur = curNext;
        while(cur!=null){
            curNext = this.cur.next;
            this.cur.next = head;
            this.head = this.cur;
            cur = curNext;
        }
        return head;
    }

    //12. 给定一个头结点为 head 的非空单链表，返回链表的中间结点。
    //如果有两个中间结点，则返回第二个中间结点。
    public ListNode middleNode( ) {
        if(head==null){
            return null;
        }
        if(head.next==null){
            return head;
        }
        ListNode fast = head;
        ListNode slow = head;
        while(fast!=null && fast.next!=null){
            fast=fast.next.next;
            slow=slow.next;
        }
        return slow;
    }
    //13. 输入一个链表，输出该链表中倒数第k个结点。
    public ListNode FindKthToTail(int k) {
        if(k<0 || head==null){
            return null;
        }
        ListNode fast = head;
        ListNode slow = head;
        //快的先走k-1布
        while(k-1!=0){
            if(fast.next!=null){
                fast = fast.next;
                k--;
            }else{
                System.out.println("k的值过大");
                return null;
            }

        }
        //慢的和快的一起走
        while(fast.next!=null){
            fast=fast.next;
            slow=slow.next;

        }
        return slow;
    }

    //15.现有一链表的头指针 ListNode* pHead，给一定值x，编写一段代码将所有小于x的结点排在其余结点之前，
    //且不能改变原来的数据顺序，返回重新排列后的链表的头指针。
    public ListNode partition(int x) {
        if(head == null){
            return null;
        }
        ListNode bs = null;
        ListNode be = null;
        ListNode as = null;
        ListNode ae = null;
        while (head !=null){
            if(head.val<x){
                if(bs==null){
                    //如果是第一次插入
                    bs=head;
                    be=head;
                }else{
                    //如果不是第一次插入
                    be.next=head;
                    be=be.next;
                }
            }else{
                //需要判断是不是第一次插入
                if(as==null){
                    as=head;
                    ae=head;
                }else{
                    //不是第一次插入
                    ae.next=head;
                    ae=ae.next;
                }
            }
            head=head.next;
        }
        if(bs == null){
            return as;
        }
        be.next=as;
        //预防最后一个节点值不为null
        if(as!=null){
            ae.next=null;
        }
        return bs;
    }
    //16.在一个排序的链表中，存在重复的结点，请删除该链表中重复的结点，重复的结点不保留，返回链表头指针。
    // 例如，链表1->2->3->3->4->4->5 处理后为 1->2->5
    public ListNode deleteDuplication( ) {
        
        return null;
    }


}
